home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 2010 April / PCWorld0410.iso / hity wydania / Ubuntu 9.10 PL / karmelkowy-koliberek-desktop-9.10-i386-PL.iso / casper / filesystem.squashfs / usr / lib / python2.6 / compiler / symbols.py < prev    next >
Text File  |  2009-11-02  |  14KB  |  462 lines
  1. """Module symbol-table generator"""
  2.  
  3. from compiler import ast
  4. from compiler.consts import SC_LOCAL, SC_GLOBAL, SC_FREE, SC_CELL, SC_UNKNOWN
  5. from compiler.misc import mangle
  6. import types
  7.  
  8.  
  9. import sys
  10.  
  11. MANGLE_LEN = 256
  12.  
  13. class Scope:
  14.     # XXX how much information do I need about each name?
  15.     def __init__(self, name, module, klass=None):
  16.         self.name = name
  17.         self.module = module
  18.         self.defs = {}
  19.         self.uses = {}
  20.         self.globals = {}
  21.         self.params = {}
  22.         self.frees = {}
  23.         self.cells = {}
  24.         self.children = []
  25.         # nested is true if the class could contain free variables,
  26.         # i.e. if it is nested within another function.
  27.         self.nested = None
  28.         self.generator = None
  29.         self.klass = None
  30.         if klass is not None:
  31.             for i in range(len(klass)):
  32.                 if klass[i] != '_':
  33.                     self.klass = klass[i:]
  34.                     break
  35.  
  36.     def __repr__(self):
  37.         return "<%s: %s>" % (self.__class__.__name__, self.name)
  38.  
  39.     def mangle(self, name):
  40.         if self.klass is None:
  41.             return name
  42.         return mangle(name, self.klass)
  43.  
  44.     def add_def(self, name):
  45.         self.defs[self.mangle(name)] = 1
  46.  
  47.     def add_use(self, name):
  48.         self.uses[self.mangle(name)] = 1
  49.  
  50.     def add_global(self, name):
  51.         name = self.mangle(name)
  52.         if name in self.uses or name in self.defs:
  53.             pass # XXX warn about global following def/use
  54.         if name in self.params:
  55.             raise SyntaxError, "%s in %s is global and parameter" % \
  56.                   (name, self.name)
  57.         self.globals[name] = 1
  58.         self.module.add_def(name)
  59.  
  60.     def add_param(self, name):
  61.         name = self.mangle(name)
  62.         self.defs[name] = 1
  63.         self.params[name] = 1
  64.  
  65.     def get_names(self):
  66.         d = {}
  67.         d.update(self.defs)
  68.         d.update(self.uses)
  69.         d.update(self.globals)
  70.         return d.keys()
  71.  
  72.     def add_child(self, child):
  73.         self.children.append(child)
  74.  
  75.     def get_children(self):
  76.         return self.children
  77.  
  78.     def DEBUG(self):
  79.         print >> sys.stderr, self.name, self.nested and "nested" or ""
  80.         print >> sys.stderr, "\tglobals: ", self.globals
  81.         print >> sys.stderr, "\tcells: ", self.cells
  82.         print >> sys.stderr, "\tdefs: ", self.defs
  83.         print >> sys.stderr, "\tuses: ", self.uses
  84.         print >> sys.stderr, "\tfrees:", self.frees
  85.  
  86.     def check_name(self, name):
  87.         """Return scope of name.
  88.  
  89.         The scope of a name could be LOCAL, GLOBAL, FREE, or CELL.
  90.         """
  91.         if name in self.globals:
  92.             return SC_GLOBAL
  93.         if name in self.cells:
  94.             return SC_CELL
  95.         if name in self.defs:
  96.             return SC_LOCAL
  97.         if self.nested and (name in self.frees or name in self.uses):
  98.             return SC_FREE
  99.         if self.nested:
  100.             return SC_UNKNOWN
  101.         else:
  102.             return SC_GLOBAL
  103.  
  104.     def get_free_vars(self):
  105.         if not self.nested:
  106.             return ()
  107.         free = {}
  108.         free.update(self.frees)
  109.         for name in self.uses.keys():
  110.             if name not in self.defs and name not in self.globals:
  111.                 free[name] = 1
  112.         return free.keys()
  113.  
  114.     def handle_children(self):
  115.         for child in self.children:
  116.             frees = child.get_free_vars()
  117.             globals = self.add_frees(frees)
  118.             for name in globals:
  119.                 child.force_global(name)
  120.  
  121.     def force_global(self, name):
  122.         """Force name to be global in scope.
  123.  
  124.         Some child of the current node had a free reference to name.
  125.         When the child was processed, it was labelled a free
  126.         variable.  Now that all its enclosing scope have been
  127.         processed, the name is known to be a global or builtin.  So
  128.         walk back down the child chain and set the name to be global
  129.         rather than free.
  130.  
  131.         Be careful to stop if a child does not think the name is
  132.         free.
  133.         """
  134.         self.globals[name] = 1
  135.         if name in self.frees:
  136.             del self.frees[name]
  137.         for child in self.children:
  138.             if child.check_name(name) == SC_FREE:
  139.                 child.force_global(name)
  140.  
  141.     def add_frees(self, names):
  142.         """Process list of free vars from nested scope.
  143.  
  144.         Returns a list of names that are either 1) declared global in the
  145.         parent or 2) undefined in a top-level parent.  In either case,
  146.         the nested scope should treat them as globals.
  147.         """
  148.         child_globals = []
  149.         for name in names:
  150.             sc = self.check_name(name)
  151.             if self.nested:
  152.                 if sc == SC_UNKNOWN or sc == SC_FREE \
  153.                    or isinstance(self, ClassScope):
  154.                     self.frees[name] = 1
  155.                 elif sc == SC_GLOBAL:
  156.                     child_globals.append(name)
  157.                 elif isinstance(self, FunctionScope) and sc == SC_LOCAL:
  158.                     self.cells[name] = 1
  159.                 elif sc != SC_CELL:
  160.                     child_globals.append(name)
  161.             else:
  162.                 if sc == SC_LOCAL:
  163.                     self.cells[name] = 1
  164.                 elif sc != SC_CELL:
  165.                     child_globals.append(name)
  166.         return child_globals
  167.  
  168.     def get_cell_vars(self):
  169.         return self.cells.keys()
  170.  
  171. class ModuleScope(Scope):
  172.     __super_init = Scope.__init__
  173.  
  174.     def __init__(self):
  175.         self.__super_init("global", self)
  176.  
  177. class FunctionScope(Scope):
  178.     pass
  179.  
  180. class GenExprScope(Scope):
  181.     __super_init = Scope.__init__
  182.  
  183.     __counter = 1
  184.  
  185.     def __init__(self, module, klass=None):
  186.         i = self.__counter
  187.         self.__counter += 1
  188.         self.__super_init("generator expression<%d>"%i, module, klass)
  189.         self.add_param('.0')
  190.  
  191.     def get_names(self):
  192.         keys = Scope.get_names(self)
  193.         return keys
  194.  
  195. class LambdaScope(FunctionScope):
  196.     __super_init = Scope.__init__
  197.  
  198.     __counter = 1
  199.  
  200.     def __init__(self, module, klass=None):
  201.         i = self.__counter
  202.         self.__counter += 1
  203.         self.__super_init("lambda.%d" % i, module, klass)
  204.  
  205. class ClassScope(Scope):
  206.     __super_init = Scope.__init__
  207.  
  208.     def __init__(self, name, module):
  209.         self.__super_init(name, module, name)
  210.  
  211. class SymbolVisitor:
  212.     def __init__(self):
  213.         self.scopes = {}
  214.         self.klass = None
  215.  
  216.     # node that define new scopes
  217.  
  218.     def visitModule(self, node):
  219.         scope = self.module = self.scopes[node] = ModuleScope()
  220.         self.visit(node.node, scope)
  221.  
  222.     visitExpression = visitModule
  223.  
  224.     def visitFunction(self, node, parent):
  225.         if node.decorators:
  226.             self.visit(node.decorators, parent)
  227.         parent.add_def(node.name)
  228.         for n in node.defaults:
  229.             self.visit(n, parent)
  230.         scope = FunctionScope(node.name, self.module, self.klass)
  231.         if parent.nested or isinstance(parent, FunctionScope):
  232.             scope.nested = 1
  233.         self.scopes[node] = scope
  234.         self._do_args(scope, node.argnames)
  235.         self.visit(node.code, scope)
  236.         self.handle_free_vars(scope, parent)
  237.  
  238.     def visitGenExpr(self, node, parent):
  239.         scope = GenExprScope(self.module, self.klass);
  240.         if parent.nested or isinstance(parent, FunctionScope) \
  241.                 or isinstance(parent, GenExprScope):
  242.             scope.nested = 1
  243.  
  244.         self.scopes[node] = scope
  245.         self.visit(node.code, scope)
  246.  
  247.         self.handle_free_vars(scope, parent)
  248.  
  249.     def visitGenExprInner(self, node, scope):
  250.         for genfor in node.quals:
  251.             self.visit(genfor, scope)
  252.  
  253.         self.visit(node.expr, scope)
  254.  
  255.     def visitGenExprFor(self, node, scope):
  256.         self.visit(node.assign, scope, 1)
  257.         self.visit(node.iter, scope)
  258.         for if_ in node.ifs:
  259.             self.visit(if_, scope)
  260.  
  261.     def visitGenExprIf(self, node, scope):
  262.         self.visit(node.test, scope)
  263.  
  264.     def visitLambda(self, node, parent, assign=0):
  265.         # Lambda is an expression, so it could appear in an expression
  266.         # context where assign is passed.  The transformer should catch
  267.         # any code that has a lambda on the left-hand side.
  268.         assert not assign
  269.  
  270.         for n in node.defaults:
  271.             self.visit(n, parent)
  272.         scope = LambdaScope(self.module, self.klass)
  273.         if parent.nested or isinstance(parent, FunctionScope):
  274.             scope.nested = 1
  275.         self.scopes[node] = scope
  276.         self._do_args(scope, node.argnames)
  277.         self.visit(node.code, scope)
  278.         self.handle_free_vars(scope, parent)
  279.  
  280.     def _do_args(self, scope, args):
  281.         for name in args:
  282.             if type(name) == types.TupleType:
  283.                 self._do_args(scope, name)
  284.             else:
  285.                 scope.add_param(name)
  286.  
  287.     def handle_free_vars(self, scope, parent):
  288.         parent.add_child(scope)
  289.         scope.handle_children()
  290.  
  291.     def visitClass(self, node, parent):
  292.         parent.add_def(node.name)
  293.         for n in node.bases:
  294.             self.visit(n, parent)
  295.         scope = ClassScope(node.name, self.module)
  296.         if parent.nested or isinstance(parent, FunctionScope):
  297.             scope.nested = 1
  298.         if node.doc is not None:
  299.             scope.add_def('__doc__')
  300.         scope.add_def('__module__')
  301.         self.scopes[node] = scope
  302.         prev = self.klass
  303.         self.klass = node.name
  304.         self.visit(node.code, scope)
  305.         self.klass = prev
  306.         self.handle_free_vars(scope, parent)
  307.  
  308.     # name can be a def or a use
  309.  
  310.     # XXX a few calls and nodes expect a third "assign" arg that is
  311.     # true if the name is being used as an assignment.  only
  312.     # expressions contained within statements may have the assign arg.
  313.  
  314.     def visitName(self, node, scope, assign=0):
  315.         if assign:
  316.             scope.add_def(node.name)
  317.         else:
  318.             scope.add_use(node.name)
  319.  
  320.     # operations that bind new names
  321.  
  322.     def visitFor(self, node, scope):
  323.         self.visit(node.assign, scope, 1)
  324.         self.visit(node.list, scope)
  325.         self.visit(node.body, scope)
  326.         if node.else_:
  327.             self.visit(node.else_, scope)
  328.  
  329.     def visitFrom(self, node, scope):
  330.         for name, asname in node.names:
  331.             if name == "*":
  332.                 continue
  333.             scope.add_def(asname or name)
  334.  
  335.     def visitImport(self, node, scope):
  336.         for name, asname in node.names:
  337.             i = name.find(".")
  338.             if i > -1:
  339.                 name = name[:i]
  340.             scope.add_def(asname or name)
  341.  
  342.     def visitGlobal(self, node, scope):
  343.         for name in node.names:
  344.             scope.add_global(name)
  345.  
  346.     def visitAssign(self, node, scope):
  347.         """Propagate assignment flag down to child nodes.
  348.  
  349.         The Assign node doesn't itself contains the variables being
  350.         assigned to.  Instead, the children in node.nodes are visited
  351.         with the assign flag set to true.  When the names occur in
  352.         those nodes, they are marked as defs.
  353.  
  354.         Some names that occur in an assignment target are not bound by
  355.         the assignment, e.g. a name occurring inside a slice.  The
  356.         visitor handles these nodes specially; they do not propagate
  357.         the assign flag to their children.
  358.         """
  359.         for n in node.nodes:
  360.             self.visit(n, scope, 1)
  361.         self.visit(node.expr, scope)
  362.  
  363.     def visitAssName(self, node, scope, assign=1):
  364.         scope.add_def(node.name)
  365.  
  366.     def visitAssAttr(self, node, scope, assign=0):
  367.         self.visit(node.expr, scope, 0)
  368.  
  369.     def visitSubscript(self, node, scope, assign=0):
  370.         self.visit(node.expr, scope, 0)
  371.         for n in node.subs:
  372.             self.visit(n, scope, 0)
  373.  
  374.     def visitSlice(self, node, scope, assign=0):
  375.         self.visit(node.expr, scope, 0)
  376.         if node.lower:
  377.             self.visit(node.lower, scope, 0)
  378.         if node.upper:
  379.             self.visit(node.upper, scope, 0)
  380.  
  381.     def visitAugAssign(self, node, scope):
  382.         # If the LHS is a name, then this counts as assignment.
  383.         # Otherwise, it's just use.
  384.         self.visit(node.node, scope)
  385.         if isinstance(node.node, ast.Name):
  386.             self.visit(node.node, scope, 1) # XXX worry about this
  387.         self.visit(node.expr, scope)
  388.  
  389.     # prune if statements if tests are false
  390.  
  391.     _const_types = types.StringType, types.IntType, types.FloatType
  392.  
  393.     def visitIf(self, node, scope):
  394.         for test, body in node.tests:
  395.             if isinstance(test, ast.Const):
  396.                 if type(test.value) in self._const_types:
  397.                     if not test.value:
  398.                         continue
  399.             self.visit(test, scope)
  400.             self.visit(body, scope)
  401.         if node.else_:
  402.             self.visit(node.else_, scope)
  403.  
  404.     # a yield statement signals a generator
  405.  
  406.     def visitYield(self, node, scope):
  407.         scope.generator = 1
  408.         self.visit(node.value, scope)
  409.  
  410. def list_eq(l1, l2):
  411.     return sorted(l1) == sorted(l2)
  412.  
  413. if __name__ == "__main__":
  414.     import sys
  415.     from compiler import parseFile, walk
  416.     import symtable
  417.  
  418.     def get_names(syms):
  419.         return [s for s in [s.get_name() for s in syms.get_symbols()]
  420.                 if not (s.startswith('_[') or s.startswith('.'))]
  421.  
  422.     for file in sys.argv[1:]:
  423.         print file
  424.         f = open(file)
  425.         buf = f.read()
  426.         f.close()
  427.         syms = symtable.symtable(buf, file, "exec")
  428.         mod_names = get_names(syms)
  429.         tree = parseFile(file)
  430.         s = SymbolVisitor()
  431.         walk(tree, s)
  432.  
  433.         # compare module-level symbols
  434.         names2 = s.scopes[tree].get_names()
  435.  
  436.         if not list_eq(mod_names, names2):
  437.             print
  438.             print "oops", file
  439.             print sorted(mod_names)
  440.             print sorted(names2)
  441.             sys.exit(-1)
  442.  
  443.         d = {}
  444.         d.update(s.scopes)
  445.         del d[tree]
  446.         scopes = d.values()
  447.         del d
  448.  
  449.         for s in syms.get_symbols():
  450.             if s.is_namespace():
  451.                 l = [sc for sc in scopes
  452.                      if sc.name == s.get_name()]
  453.                 if len(l) > 1:
  454.                     print "skipping", s.get_name()
  455.                 else:
  456.                     if not list_eq(get_names(s.get_namespace()),
  457.                                    l[0].get_names()):
  458.                         print s.get_name()
  459.                         print sorted(get_names(s.get_namespace()))
  460.                         print sorted(l[0].get_names())
  461.                         sys.exit(-1)
  462.